#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-07-24 5:41 下午
# @Author  : yangdy
# @File    : N叉树的层序遍历
# @Software: PyCharmCE
from typing import List


"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""


class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return []
        ans, que, i = [[root.val]], [[root]], 0
        while que[i]:
            que_new = []
            ans_new = []
            for x in que[i]:
                if x:
                    for y in x.children:
                        if y:
                            que_new.append(y)
                            ans_new.append(y.val)
            que.append(que_new)
            ans.append(ans_new)
            i += 1
        while not ans[i]:
            ans.pop()
            i -= 1

        return ans
